/*
 *https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/
 *lc2316. 统计无向图中无法互相到达点对数
 *medium 吴朝泽 2024.9.28
 *并查集
 创建一个 union_find 类，初始化每个节点的父节点为自身，并且每个节点的初始大小为 1，连通分量数量为节点总数
 遍历给定的边，将每条边连接的两个节点进行合并。使用 pair 方法来合并两个节点，确保较小的树附加到较大的树上以保持平衡
 在遍历所有节点时，使用 find 方法找到每个节点的根节点，并统计每个根节点对应的组件大小。用一个数组 componentSizes 来记录每个组件的大小
 维护一个变量 totalNodes 来跟踪当前已处理的节点数量。对于每个组件，如果它的大小大于 0，就可以与之前的所有节点形成配对。
 计算方式是将当前组件的大小与已处理的节点总数相乘，并累加到 count 中
*/

class union_find {
    vector<int> parent;  // 存储每个节点的父节点
    vector<int> size;    // 用于跟踪每个连通分量的大小
    int group;           // 连通分量的数量

public:
    // 构造函数，初始化节点及其父节点
    union_find(int n) : parent(n), size(n, 1), group(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 每个节点初始为自己的父节点
        }
    }

    // 联合操作，用于合并两个组件
    void pair(int index1, int index2) {
        int root1 = find(index1);  // 找到index1的根
        int root2 = find(index2);  // 找到index2的根
        if (root1 != root2) {       // 如果两个节点不在同一组
            // 将较小的树附加到较大的树下
            if (size[root1] < size[root2]) {
                swap(root1, root2);
            }
            parent[root2] = root1;  // 更新根节点
            size[root1] += size[root2];  // 更新新的根的大小
            --group;  // 减少组数
        }
    }

    // 查找操作，带路径压缩
    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);  // 路径压缩
        }
        return parent[index];  // 返回根节点
    }

    // 获取包含指定索引的组件的大小
    int getSize(int index) {
        return size[find(index)];  // 返回根节点的大小
    }

    // 返回组数
    int group_count() {
        return group;  // 返回当前组数
    }
};

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        union_find uf(n);  // 初始化并查集
        long long count = 0;  // 用于计数

        // 根据边创建联合
        for (auto& edge : edges) {
            uf.pair(edge[0], edge[1]);  // 合并两个节点
        }

        // 跟踪每个组件的大小
        vector<long long> componentSizes(n, 0);
        for (int i = 0; i < n; ++i) {
            int root = uf.find(i);  // 找到每个节点的根
            componentSizes[root] += 1;  // 统计每个组件中的节点数量
        }

        // 计算总对数
        long long totalNodes = 0;  // 记录已处理的节点总数
        for (int i = 0; i < n; ++i) {
            if (componentSizes[i] > 0) {  // 仅考虑非零大小的组件
                count += totalNodes * componentSizes[i];  // 计算与已处理组件的对数
                totalNodes += componentSizes[i];  // 更新总节点数
            }
        }

        return count;  // 返回总对数
    }
};